
# 两个链表合并并按照升序排序
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    head = ListNode()
    cur = head
    while l1 and l2:
        if l1.val <= l2.val:  # l1比较小
            cur.next = l1
            cur = l1
            l1 = l1.next
        else:
            cur.next = l2
            cur = l2
            l2 = l2.next

    # 剩下的两个可以使用if语句
    while l1:  # 剩下的都是l1
        cur.next = l1
        cur = l1
        l1 = l1.next
    while l2:
        cur.next = l2
        cur = l2
        l2 = l2.next

    return head.next


# 递归方法解决问题.递归的方法往往十分精妙
def mergeTwoLists(l1,l2):
    if l1 == None:
        return l2
    elif l2 == None:
        return l1
    elif l1.val < l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

